class Solution {
    //当前字符串要变成回文,那只要把不一样的找出来就好了即:求出反过来的字符串和当前字符串的最长公共子序列,然后减一下

// 如 leetcode 和 edocteel 的最长公共子序列是  e t e ,长度为3,  即 8-3 = 5.此时找到ete是回文串了,不用理了,剩下5个,l e c o d
//所以我们要操作5次,分别找到合适的位置在原字符串中插入l,e,c,o,d
//leedoctocdeel 
public:
    int minInsertions(string s) {
        int n=s.size();
        string t=s;
        vector<vector<int>>dp(n+1,vector<int>(n+1,0));
        reverse(t.begin(),t.end());
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(s[i-1]==t[j-1])
                dp[i][j]+=dp[i-1][j-1]+1;
                else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return n-dp[n][n];
    }
};